<!DOCTYPE HTML PUBLIC "-//W3C//DTD XHTML 1.0 Frameset//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-frameset.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">


	<title>A Graph Problem</title>
	<style>
		tt { font-weight: bold; font-size: 12pt; }	
		pre { font-weight: bold; font-size: 12pt; }	
		h2 { color: #0070E8; }
		p { text-align: justify; }
	</style>
</head><body>
<h1 align="center"><span style="background-color: rgb(0, 96, 240); color: rgb(192, 255, 255);">&nbsp;A Graph Problem&nbsp;</span></h1>
<h3 align="center">Time limit: 2s</h3>
<p>
Given an undirected graph of the following form with <em>n</em> nodes, <em>1 &#8804; n &#8804; 76</em>:
<br>
<br>
  <img src="acm-11069_archivos/p11069.png" hspace="10">
<br>
<br>
Your task is to calculate the number of subsets of nodes of the graph with the following properties:
</p><ul>
	<li> no nodes in the subset should be connected </li>
	<li> it shouldn't be possible to add further nodes to the subset without violating the first condition </li>
</ul>
	For a graph with <em>5</em> nodes the number of subsets which fulfill the above conditions is <em>4</em>. The subsets are
	<em>{1,3,5},{2,4},{2,5},{1,4}</em>.


<p></p>

<h2>Input</h2>
<p>
The input will consist of a sequence of numbers <em>n</em>,<em>1 &#8804; n &#8804; 76</em>. Each number will be on a separate line. The input will be terminated by EOF.
</p>

<h2>Output</h2>
<p>
Output the number of subsets as described above on a single line. The number of all subsets will be less than <em>2^31</em>.
</p>

<h2>Sample input</h2>
<pre>1
2
3
4
5
30
</pre>

<h2>Sample output</h2>
<pre>1
2
2
3
4
4410
</pre>

<br clear="all"><br>
<hr>
FAU Local Summer Contest 2005
<br>
Author: Der General
</body></html>